package com.nowcoder.code.hjnc;

public class NC_86_MT02 {
    /**
     * @param matrix int整型二维数组
     * @param target int整型
     * @return bool布尔型
     */
    public boolean searchMatrix(int[][] matrix, int target) {

        int start = 0, end = matrix.length - 1;
        int mid;
        while (start <= end) {
            mid = (start + end) >> 1;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        mid = (start + end) >> 1;

        int im = Math.max(mid, 0);
        start = 0;
        end = matrix[im].length - 1;

        while (start <= end) {
            mid = (start + end) >> 1;
            if (matrix[im][mid] == target) {
                return true;
            } else if (matrix[im][mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return matrix[im][mid] == target;
    }


    public static void main(String[] args) {
//        int[][] ints = {{1, 2, 3}, {4, 5, 6}};
//        int[][] ints = {{1}, {3}, {5}};
        int[][] ints = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
//        int[][] ints = {{1}};
        boolean r = new NC_86_MT02().searchMatrix(ints, 3);
        System.out.println(r);
    }
}